The traditional Viterbi algorithm is an efficient search for optimal sequence detection, which requires a recursive metric structure for the metric to be optimized. However, a recursive metric structure does not exist in many maximum likelihood sequence estimation (MLSE) problems. Furthermore, the traditional Viterbi algorithm experiences an exponential increase of computational complexity as the symbol pulse spread increases when applied to partial response channels.
What is needed is a Generalized Viterbi algorithm in which the metric to be optimized can be an arbitrary function. Preferably, the Generalized Viterbi algorithm will solve those MLSE problems unable to use the traditional Viterbi search, in a manner that is near optimal and efficient. Also preferably, those MLSE problems suitable for the traditional Viterbi search will be able to achieve a near optimal solution with a small fraction of the computation. More importantly, different from the traditional Viterbi search, the Generalized Viterbi search will preferably avoid an exponential increase of computation complexity as the symbol pulse spread increases when applied to partial response channels.